package topic.linklist;

/**
 * 合并两个有序链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */
public class MergeTwoLists {
    public static void main(String[] args) {
        mergeTwoLists(LinkListFactory.getFirstListNode(), LinkListFactory.getSecondListNode());
    }

    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建哑节点
        ListNode prv = new ListNode(-1);
        // 保存哑节点位置
        ListNode curr = prv;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                // 当前节点指向下一节点
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            // 替换指针为当前节点
            curr = curr.next;
        }
        // 接入链表后续节点
        curr.next = l1 == null ? l2 : l1;
        return prv.next;
    }
}
